In information networks, data are often transmitted over the network in groupings called “frames” or “packets.” Devices connected to the network may communicate with each other by passing data packets between each other over the network. Transmission is achieved by apportioning the transmitted data into a number of packets, with each packet including “header” information that allows for reconstruction of the data upon receipt by the desired destination device. The header information will include addressing information about the destination device in order for the packet to be forwarded to the desired destination device.
Within the network are forwarding devices (e.g., routers, gateways, switches) that forward packets through the network to the destination device, according to the addressing information contained in the packet header. These forwarding devices use the addressing information stored in the packet as part of the decision process in determining how to forward the packet over the network. This determination has been commonly performed using a forwarding table stored in the forwarding device. The forwarding table provides the appropriate forwarding information based on the destination address specified in the packet (for example, the network address of the next forwarding device likely to be helpful in routing the packet to its final destination).
With the increasing use of packet-switched data networks to carry various types of communications—for example, telephony, real-time video, multicasting, and file-type data (e-mail, file transfers)—selective switching of data packets is becoming important in order to implement different Quality of Service (QoS) levels for each type of communication. For example, video communications requires high bandwidth and timely delivery of data (in order to resolve the video images in real-time and in the proper sequence), while file-type transmissions need not be delivered immediately. These data steams streams may be identified by different protocols used for their transmission. Also, network providers would like to be able to offer differential levels of service in order to accommodate customers that are willing to pay more for enhanced transmission capacity or special network configurations (e.g., virtual private networks).
One way to account for the more advanced forwarding considerations described above is by performing packet “classification”—that is, to determine the nature of the data being transmitted and then determine an appropriate way to handle the data as it traverses the network. Classification requires further analysis of the contents of the packet, and such analysis can be time consuming in the context of a switching process, particularly in light of the numerous different types of data streams in use (and being developed). In order to achieve packet classification in this environment, it has been believed that dedicated hardware or powerful general-purpose processors would be required. Neither of these implementations is ideal: dedicated classification hardware is not easily upgradable for processing new developments; and powerful general-purpose processors (while flexible) incur expenses that may make the device cost-prohibitive.